package com.ddd.demo.lee.排序;

import java.util.Arrays;

public class 桶排序 {

    // 桶排序函数
    public static void bucketSort(double[] arr) {
        int n = arr.length;
        // 创建桶
        double[] bucket = new double[n];
        // 初始化桶
        Arrays.fill(bucket, 0);
        // 将元素分配到相应的桶中
        for (int i = 0; i < n; i++) {
            int bucketIndex = (int) (arr[i] * n);
            bucket[bucketIndex]++;
        }
        // 对每个桶进行排序
        for (int i = 0; i < n; i++) {
            if (bucket[i] > 0) {
                Arrays.sort(bucket, i, i + 1);
            }
        }
        // 合并桶中的元素
        int index = 0;
        for (int i = 0; i < n; i++) {
            while (bucket[i] > 0) {
                arr[index++] = bucket[i];
                bucket[i]--;
            }
        }
    }

    // 测试案例
    public static void main(String[] args) {
        double[] arr = {0.5, 0.84, 2.18, 3.25, 4.5};
        System.out.println("排序前的数组为：");
        for (double num : arr) {
            System.out.print(num + " ");
        }
        bucketSort(arr);
        System.out.println("\n 排序后的数组为：");
        for (double num : arr) {
            System.out.print(num + " ");
        }
    }
}
